# 模拟
class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid = [[0] * n for i in range(m)]
        # 先找出墙和警卫位置
        for x in walls:
            grid[x[0]][x[1]] = 1
        for y in guards:
            grid[y[0]][y[1]] = 1

        def search(i, j):
            for left in range(j - 1, -1, -1):
                if grid[i][left] != 1:
                    grid[i][left] = 2
                else:
                    break
            for right in range(j + 1, n):
                if grid[i][right] != 1:
                    grid[i][right] = 2
                else:
                    break
            for up in range(i - 1, -1, -1):
                if grid[up][j] != 1:
                    grid[up][j] = 2
                else:
                    break
            for down in range(i + 1, m):
                if grid[down][j] != 1:
                    grid[down][j] = 2
                else:
                    break
        # 标记警卫看到的位置
        for y in guards:
            search(y[0], y[1])
        
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    res += 1
        return res
# 灵神代码
# 左右上下
DIRS = (0, -1), (0, 1), (-1, 0), (1, 0)

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        guarded = [[0] * n for _ in range(m)]

        # 标记警卫格子、墙格子
        for x, y in guards:
            guarded[x][y] = -1
        for x, y in walls:
            guarded[x][y] = -1

        # 遍历警卫
        for x0, y0 in guards:
            # 遍历视线方向（左右上下）
            for dx, dy in DIRS:
                # 视线所及之处，被保卫
                x, y = x0 + dx, y0 + dy
                while 0 <= x < m and 0 <= y < n and guarded[x][y] != -1:
                    guarded[x][y] = 1  # 被保卫
                    x += dx
                    y += dy

        # 统计没被保卫（值为 0）的格子数
        return sum(row.count(0) for row in guarded)